Wilson's Theorem

Theorem

An integer \(n > 1\) is prime if and only if:

\[ (n - 1)! \equiv -1 \pmod n.\]

Proof

Let \(n\) by prime. This means that \(\mathbb{Z}_n\) is a field (this field) and hence that there are no non-zero zero divisors.

Hence, if \(x \in \mathbb{Z}_p\) then

\[\begin{align*} x^2 - 1 = 0 &\iff (x - 1)(x + 1) = 0 \\ &\iff x - 1 = 0 \ \text{or} \ x + 1 = 0 \\ &\iff x = 1 \ \text{or} \ x = -1. \end{align*}\]

This means \(x\) is part of the residue classes of \(1\) or \(n - 1\) if and only if it is self inverse (which is equivalent to \(x^2 = 1\)). Hence, in the expression of \((n - 1)!\), every other term must be able to be paired with its inverse by commuting the terms

\[\begin{align*} (n - 1)! &\equiv 1 \times 2 \times 3 \times \dots \times (n - 1) \\ &\equiv 1 \times (n - 1) \pmod n \\ &\equiv (n - 1) \pmod n \\ &\equiv -1 \pmod n. \end{align*}\]

Now for the converse we assume that \(n\) is composite. This means that \(n\) can be expressed as a product of two numbers \(a, b\) with \(2 \leq a, b \leq n - 1\). This means that \((n - 1)!\) includes both \(a\) and \(b\) when written out explicitly, and is thus a multiple of \(n\). Hence \((n - 1)! \equiv 0 \pmod n\). The only case in which this fails to be true is when \(a = b\) in the only such factorisation, however in this case, for \(n \geq 3^2\), there is necessarily at least one other term which contains a factor of \(a\) (for example \(6\) when considering \(3^2\)) and if \(n = 4\), then \(3! = 6 \equiv 2 \mod 4\), so the theorem holds in this case too.

Corollary

If \(n\) is not prime and \(n \neq 4\), then:

\[ (n - 1)! \equiv 0 \pmod n.\]

If \(n = 4\) then:

\[ (n - 1)! \equiv 2 \pmod 4.\]

This is apparent from the proof of Wilson's theorem, and the use of the special case for \(n = 4\).